ABSTRACT
In this paper, we study the adversarial attacks on influence maximization under dynamic influence propagation models in social networks. In particular, given a known seed set S, the problem is to minimize the influence spread from S by deleting a limited number of nodes and edges. This problem reflects many application scenarios, such as blocking virus (e.g. COVID-19) propagation in social networks by quarantine and vaccination, blocking rumor spread by freezing fake accounts, or attacking competitor's influence by incentivizing some users to ignore the information from the competitor. In this paper, under the linear threshold model, we adapt the reverse influence sampling approach and provide efficient algorithms of sampling valid reverse reachable paths to solve the problem. We present three different design choices on reverse sampling, which all guarantee 1/2 - ϵ approximation (for any small ϵ >0) and an efficient running time. © 2023 ACM.
ABSTRACT
Identification of a small group of individuals based on their maximal influence cascade is influence maximization. During the COVID-19 pandemic, discussion forums on the Massive Open Online Course (MOOC) platform have become a paramount interaction medium among learners, and the identification of influential learners evolved as a substantial research issue. In this research paper, an optimization function based on an independent cascade is established for the discussion forum influence maximization problem. A modified version of the BAT algorithm is proposed which memorizes the bad experience of the BAT. The proposed Modified algorithm helps the BAT to remember the worst location that has already been traversed for a reliable estimation in an optimized manner while exploring the best solution. Further, the performance of BAT and Modified BAT for influence maximization on the discussion forum network of a MOOC platform is evaluated which shows the excellent performance of modified BAT. Convergence graph for different populations on deviating probability depicts the effective performance of modified BAT over generic BAT algorithm. © 2022 ACM.
ABSTRACT
Identifying a set of critical nodes with high propagation in complex networks to achieve maximum influence is an important task in the field of complex network research, especially in the background of the current rapid global spread of COVID-19. In view of this, some scholars believe that nodes with high importance in the network have stronger propagation, and many classical methods are proposed to evaluate node importance. However, this approach makes it difficult to ensure that the selected spreaders are dispersed in the network, which greatly affects the propagation ability. The VoteRank algorithm uses a voting-based method to identify nodes with strong propagation in the network, but there are some deficiencies. Here, we solve this problem by proposing the DILVoteRank algorithm. The VoteRank algorithm cannot properly reflect the importance of nodes in the network topology. Based on this, we redefine the initial voting ability of nodes in the VoteRank algorithm and introduce the degree and importance of the line (DIL) ranking method to calculate the voting score so that the algorithm can better reflect the importance of nodes in the network structure. In addition, the weakening mechanism of the VoteRank algorithm only weakens the information of neighboring nodes of the selected nodes, which does not guarantee that the identified initial spreaders are sufficiently dispersed in the network. On this basis, we consider all the neighbors nodes of the node's nearest and next nearest neighbors, so that the crucial spreaders identified by our algorithm are more widely distributed in the network with the same initial node ratio. In order to test the algorithm performance, we simulate the DILVoteRank algorithm with six other benchmark algorithms in 12 real-world network datasets based on two propagation dynamics model. The experimental results show that our algorithm identifies spreaders that achieve stronger propagation ability and propagation scale and with more stability compared to other benchmark algorithms.
ABSTRACT
Mathematical approaches, such as compartmental models and agent-based models, have been utilized for modeling the spread of the infectious diseases in the computational epidemiology. However, the role of social network structure for transmission of diseases is not explicitly considered in these models. In this paper, the influence maximization problem, considering the diseases starting at some initial nodes with the potential to maximize the spreading in a social network, is adapted to model the spreading process. This approach includes the analysis of network structure and the modeling of connections among individuals with probabilities to be infected. Additionally, individual behaviors that change along the time and eventually influence the spreading process are also included. These considerations are formulated by integer optimization models. Simulation results, based on the randomly generated networks and a local community network under the COVID-19, are performed to validate the effectiveness of the proposed models, and their relationships to the classic compartmental models.
ABSTRACT
Ongoing COVID-19 pandemic poses many challenges to the research of artificial intelligence. Epidemics are important in network science for modeling disease spread over networks of contacts between individuals. To prevent disease spread, it is desirable to introduce prioritized isolation of the individuals contacting many and unspecified others, or connecting different groups. Finding such influential individuals in social networks, and simulating the speed and extent of the disease spread are what we need for combating COVID-19. This article focuses on the following topics, and discusses some of the traditional and emerging research attempts: (1) topics related to epidemics in network science, such as epidemic modeling, influence maximization and temporal networks, (2) recent research of network science for COVID-19 and (3) datasets and resources for COVID-19 research.
ABSTRACT
BACKGROUND: An effective approach to containing epidemic outbreaks (e.g., COVID-19) is targeted immunization, which involves identifying "super spreaders" who play a key role in spreading disease over human contact networks. The ultimate goal of targeted immunization and other disease control strategies is to minimize the impact of outbreaks. It shares similarity with the famous influence maximization problem studied in the field of social network analysis, whose objective is to identify a group of influential individuals to maximize the influence spread over social networks. This study aims to establish the equivalence of the two problems and develop an effective methodology for targeted immunization through the use of influence maximization. METHODS: We present a concise formulation of the targeted immunization problem and show its equivalence to the influence maximization problem under the framework of the Linear Threshold diffusion model. Thus the influence maximization problem, as well as the targeted immunization problem, can be solved by an optimization approach. A Benders' decomposition algorithm is developed to solve the optimization problem for effective solutions. RESULTS: A comprehensive computational study is conducted to evaluate the performance and scalability of the optimization approach on real-world large-scale networks. Computational results show that our proposed approaches achieve more effective solutions compared to existing methods. CONCLUSIONS: We show the equivalence of the outbreak minimization and influence maximization problems and present a concise formulation for the influence maximization problem under the Linear Threshold diffusion model. A tradeoff between computational effectiveness and computational efficiency is illustrated. Our results suggest that the capability of determining the optimal group of individuals for immunization is particularly crucial for the containment of infectious disease outbreaks within a small network. Finally, our proposed methodology not only determines the optimal solutions for target immunization, but can also aid policymakers in determining the right level of immunization coverage.